{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Sub-arrays With Odd Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numOfSubarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #和为奇数的子数组数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>arr</code>&nbsp;。请你返回和为 <strong>奇数</strong>&nbsp;的子数组数目。</p>\n",
    "\n",
    "<p>由于答案可能会很大，请你将结果对&nbsp;<code>10^9 + 7</code>&nbsp;取余后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [1,3,5]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>所有的子数组为 [[1],[1,3],[1,3,5],[3],[3,5],[5]] 。\n",
    "所有子数组的和为 [1,4,9,3,8,5].\n",
    "奇数和包括 [1,9,3,5] ，所以答案为 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2 ：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [2,4,6]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>所有子数组为 [[2],[2,4],[2,4,6],[4],[4,6],[6]] 。\n",
    "所有子数组和为 [2,6,12,4,10,6] 。\n",
    "所有子数组和都是偶数，所以答案为 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [1,2,3,4,5,6,7]\n",
    "<strong>输出：</strong>16\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [100,100,99,99]\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [7]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-sub-arrays-with-odd-sum](https://leetcode.cn/problems/number-of-sub-arrays-with-odd-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-sub-arrays-with-odd-sum](https://leetcode.cn/problems/number-of-sub-arrays-with-odd-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,5]', '[2,4,6]', '[1,2,3,4,5,6,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        cur, res = 0, 0\n",
    "        for i in range(k - 1):\n",
    "            cur += arr[i]\n",
    "        for i in range(k - 1, len(arr)):\n",
    "            cur += arr[i]\n",
    "            if cur // k >= threshold:\n",
    "                res += 1\n",
    "            cur -= arr[i - k + 1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        res = 0\n",
    "        if len(arr) < k:\n",
    "            return 0\n",
    "        target = threshold * k\n",
    "        curr = sum(arr[0:k])\n",
    "        if curr >= target:\n",
    "            res += 1\n",
    "        for i in range(k, len(arr)):\n",
    "            curr = curr - arr[i - k] + arr[i]\n",
    "            if curr >= target:\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        start = 0\n",
    "        end = k-1\n",
    "        threshold *= k\n",
    "        sum = 0\n",
    "        answer = 0\n",
    "        for i in range(start,end):\n",
    "            sum += arr[i]\n",
    "        while end < len(arr):\n",
    "            sum+=arr[end]\n",
    "            if sum>=threshold:\n",
    "                answer+=1\n",
    "            sum-=arr[start]\n",
    "            start+=1\n",
    "            end+=1\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        presum=[0]\n",
    "        for a in arr:\n",
    "            presum.append(presum[-1]+a-threshold)\n",
    "        res=0\n",
    "        for i in range(len(presum)-k):\n",
    "            if presum[i+k]-presum[i]>=0:\n",
    "                res+=1 \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        res = 0\n",
    "        threshold *= k\n",
    "        ls = []\n",
    "        for i in range(k):\n",
    "            ls.append(arr.pop())\n",
    "        average = sum(ls)\n",
    "        if average >= threshold:\n",
    "            res += 1\n",
    "        while arr:\n",
    "            average -= ls.pop(0)\n",
    "            ls.append(arr.pop())\n",
    "            average += ls[-1]\n",
    "            if average >= threshold:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        num = 0\n",
    "        if len(arr) < k:\n",
    "            return 0\n",
    "        else:\n",
    "            total = sum(arr[:k])\n",
    "            if total >= k * threshold:\n",
    "                num += 1\n",
    "            for i in range(len(arr) - k):\n",
    "                total = total + (arr[i + k] - arr[i])\n",
    "                if total >= k * threshold:\n",
    "                    num += 1\n",
    "                    print('yes')\n",
    "            return num\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        target=k*threshold\n",
    "        cur=sum(arr[:k])\n",
    "        ans=0\n",
    "        n=len(arr)\n",
    "        for i in range(k,n):\n",
    "            if cur>=target:\n",
    "                ans+=1\n",
    "            cur+=arr[i]\n",
    "            cur-=arr[i-k]\n",
    "        if cur>=target:\n",
    "            ans+=1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        result = 0\n",
    "        arr.insert(0, 0)\n",
    "        pre_sums = list(accumulate(arr))\n",
    "        i, j = 0, k\n",
    "        while j < len(pre_sums):\n",
    "            tmp_sum = (pre_sums[j] - pre_sums[i])\n",
    "            if tmp_sum // k >= threshold:\n",
    "                result += 1\n",
    "            j += 1\n",
    "            i += 1\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        j=k*threshold\n",
    "        value = 0\n",
    "        count = 0\n",
    "        for i in range(len(arr)):\n",
    "            if i <k:\n",
    "                value += arr[i]\n",
    "                if i == k-1 and value >= j:\n",
    "                    count += 1\n",
    "            else:\n",
    "                value = value + arr[i] - arr[i-k]\n",
    "                if value >=j:\n",
    "                    count += 1\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        init_val = sum(arr[:k])\n",
    "        res = 0\n",
    "        len_arr = len(arr)\n",
    "        if init_val / k >= threshold:\n",
    "            res += 1\n",
    "        for i in range(k, len_arr):\n",
    "            init_val = init_val + arr[i] - arr[i - k]\n",
    "            if init_val / k >= threshold:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        ans = 0\n",
    "        temp = sum(arr[:k])\n",
    "        target = k * threshold\n",
    "        if temp >= target:\n",
    "            ans = 1\n",
    "        for i in range(k,len(arr)):\n",
    "            temp = temp - arr[i-k] + arr[i]\n",
    "            if temp >= target:\n",
    "                ans += 1\n",
    "                \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        left, right = 0, 0\n",
    "        window_sum, ans = 0, 0\n",
    "        while right < len(arr):\n",
    "            window_sum += arr[right]\n",
    "            if right - left + 1 >= k:\n",
    "                if window_sum >= k * threshold:\n",
    "                    ans += 1\n",
    "                window_sum -= arr[left]\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        valid_num = 0\n",
    "        window_sum = 0\n",
    "        for i in range(k):\n",
    "            window_sum += arr[i]\n",
    "        if window_sum/k >= threshold:\n",
    "            valid_num += 1\n",
    "        for i in range(1,len(arr)-k+1):\n",
    "            window_sum += arr[i+k-1] - arr[i-1]\n",
    "            if window_sum/k >= threshold:\n",
    "                valid_num += 1\n",
    "        return valid_num\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        ans = 0\n",
    "        pre_sum = 0\n",
    "        target = k * threshold        \n",
    "        for i in range(len(arr)) :\n",
    "            pre_sum += arr[i]\n",
    "            if i > k - 1:\n",
    "                pre_sum -= arr[i - k]\n",
    "            if i >= k - 1 and pre_sum >= target:\n",
    "                ans += 1\n",
    "\n",
    "        return ans\n",
    "       \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "    t = threshold * k\n",
    "    s = sum(arr[:k])\n",
    "    ret = 0\n",
    "    if s >= t:\n",
    "      ret += 1\n",
    "    for i in range(k, len(arr)):\n",
    "      s -= arr[i - k]\n",
    "      s += arr[i]\n",
    "      if s >= t:\n",
    "        ret += 1\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1e9+7\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        x = 1\n",
    "        y = 0\n",
    "        ans = 0\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            ans += arr[i]\n",
    "            y += (ans%2)\n",
    "            x += (1-ans%2)\n",
    "            if ans%2:\n",
    "                res+=x     \n",
    "            else:\n",
    "                res+=y\n",
    "        return int(res%MOD)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        odd = 0\n",
    "        prix = 0\n",
    "        for num in arr:\n",
    "            prix += num\n",
    "            if prix % 2 != 0:\n",
    "                odd += 1\n",
    "        return odd * (len(arr) - odd + 1) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        MODULO = 10**9 + 7\n",
    "        odd, even = 0, 1\n",
    "        prix = 0\n",
    "        for num in arr:\n",
    "            prix += num\n",
    "            if prix % 2 == 0:\n",
    "                even += 1\n",
    "            else:\n",
    "                odd += 1\n",
    "        return odd * even % MODULO"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 前缀和 + 数学\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        MODULO = 10**9 + 7\n",
    "        odd, even = 0, 1\n",
    "        subarrays = 0\n",
    "        total = 0\n",
    "        \n",
    "        for x in arr:\n",
    "            total += x\n",
    "            subarrays += (odd if total % 2 == 0 else even)\n",
    "            if total % 2 == 0:\n",
    "                even += 1\n",
    "            else:\n",
    "                odd += 1\n",
    "        \n",
    "        return subarrays % MODULO\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr) -> int:\n",
    "        length = len(arr)\n",
    "        max_int = int(1e9 + 7)\n",
    "        last = -1\n",
    "        even = []\n",
    "        for i, num in enumerate(arr):\n",
    "            if num % 2 == 1:\n",
    "                even.append(i - last)\n",
    "                last = i\n",
    "        even.append(length - last)\n",
    "        len_even = len(even)\n",
    "        if len_even == 1:\n",
    "            return 0\n",
    "        if len_even == 2:\n",
    "            return even[-1] * even[-2]\n",
    "        suf_sum_1, suf_sum_2 = even[-1], even[-2]\n",
    "        ans = even[-2] * suf_sum_1 + even[-3] * suf_sum_2\n",
    "        state = 0\n",
    "        for i in range(len_even - 3, 0, -1):\n",
    "            state ^= 1\n",
    "            if state:\n",
    "                suf_sum_1 += even[i]\n",
    "                ans += even[i - 1] * suf_sum_1\n",
    "            else:\n",
    "                suf_sum_2 += even[i]\n",
    "                ans += even[i - 1] * suf_sum_2\n",
    "        return ans % max_int"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        sums = [0]\n",
    "        for i in range(len(arr)):\n",
    "            sums.append(sums[-1] + arr[i])\n",
    "        count = {0: 0, 1: 0}\n",
    "        res = 0\n",
    "        for x in sums:\n",
    "            if x % 2:\n",
    "                res += count[0]\n",
    "                count[1] += 1\n",
    "            else:\n",
    "                res += count[1]\n",
    "                count[0] += 1\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr) -> int:\n",
    "        length = len(arr)\n",
    "        max_int = int(1e9 + 7)\n",
    "        last = -1\n",
    "        odd = []\n",
    "        for i, num in enumerate(arr):\n",
    "            if num % 2 == 1:\n",
    "                odd.append(i - last)\n",
    "                last = i\n",
    "        odd.append(length - last)\n",
    "        len_odd = len(odd)\n",
    "        if len_odd == 1:\n",
    "            return 0\n",
    "        suf_sum_1, suf_sum_2 = 0, 0\n",
    "        ans = 0\n",
    "        state = 0\n",
    "        for i in range(len_odd - 1, 0, -1):\n",
    "            state ^= 1\n",
    "            if state:\n",
    "                suf_sum_1 = suf_sum_1 + odd[i]\n",
    "                ans = (ans + odd[i - 1] * suf_sum_1) % max_int\n",
    "            else:\n",
    "                suf_sum_2 = suf_sum_2 + odd[i]\n",
    "                ans = (ans + odd[i - 1] * suf_sum_2) % max_int\n",
    "        return ans\n",
    "# class Solution:\n",
    "#     def numOfSubarrays(self, arr) -> int:\n",
    "#         max_int = int(1e9 + 7)\n",
    "#         odd, even = 0, 1\n",
    "#         pre_sum, ans = 0, 0\n",
    "#         for num in arr:\n",
    "#             pre_sum += num\n",
    "#             if pre_sum % 2 == 0:\n",
    "#                 ans = (ans + odd) % max_int\n",
    "#                 even += 1\n",
    "#             else:\n",
    "#                 ans = (ans + even) % max_int\n",
    "#                 odd += 1\n",
    "#         return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        #明天想前缀和计数思路\n",
    "        #DP思路,状态转移搞清楚\n",
    "        #奇+偶==奇\n",
    "        #偶+奇==奇\n",
    "        if arr[0]&1:\n",
    "            even=0\n",
    "            odd=1\n",
    "        else:\n",
    "            even=1\n",
    "            odd=0\n",
    "        ans=odd\n",
    "        for v in arr[1:]:\n",
    "            if v&1:\n",
    "                odd,even=even+1,odd\n",
    "            else:\n",
    "                even=even+1\n",
    "            ans+=odd\n",
    "        return ans%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = int(1e9) + 7\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        L = len(arr)\n",
    "        # 定义状态数组dp，dp[i]的含义为以arr[i]结尾的子数组中和为奇数的数量\n",
    "        dp = [0] * L\n",
    "        dp[0] = arr[0] & 1\n",
    "\n",
    "        for i in range(1, L):\n",
    "            # 若arr[i]为奇数，则其本身是一个和为奇数的子数组，同时还可以和前面arr[i - 1]\n",
    "            # 结尾的和为偶数的子数组组成和是奇数的子数组\n",
    "            if arr[i] & 1:\n",
    "                dp[i] = i - dp[i - 1] + 1\n",
    "            # 若arr[i]为偶数，则可以和前面以arr[i - 1]结尾的和为奇数的子数组组成和为\n",
    "            # 奇数的子数组\n",
    "            else:\n",
    "                dp[i] = dp[i - 1]\n",
    "            \n",
    "        return sum(dp) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = int(1e9) + 7\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        L = len(arr)\n",
    "        # 定义状态数组dp，dp[i]的含义为以arr[i]结尾的子数组中和为奇数的数量\n",
    "        dp = [0] * L\n",
    "        dp[0] = arr[0] & 1\n",
    "\n",
    "        for i in range(1, L):\n",
    "            # 若arr[i]为奇数，则其本身是一个和为奇数的子数组，同时还可以和前面arr[i - 1]\n",
    "            # 结尾的和为偶数的子数组组成和是奇数的子数组\n",
    "            if arr[i] & 1:\n",
    "                dp[i] = i - dp[i - 1] + 1\n",
    "            # 若arr[i]为偶数，则可以和前面以arr[i - 1]结尾的和为奇数的子数组组成和为\n",
    "            # 奇数的子数组\n",
    "            else:\n",
    "                dp[i] = dp[i - 1]\n",
    "            \n",
    "        return sum(dp) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        ret = 0\n",
    "        if not arr:\n",
    "            return ret\n",
    "        n = len(arr)\n",
    "        dp = [0] * n\n",
    "        if arr[0] % 2:\n",
    "            dp[0] = 1\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                ret += dp[0]\n",
    "                continue\n",
    "            elif arr[i] % 2 == 0:\n",
    "                dp[i] = dp[i - 1]\n",
    "            else:\n",
    "                dp[i] = i - dp[i - 1] + 1\n",
    "            ret = (ret + dp[i]) % (10 ** 9 + 7)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        n = len(arr)\n",
    "        dp = [0]*n\n",
    "        for i, num in enumerate(arr):\n",
    "            if num%2 == 0:\n",
    "                dp[i] = dp[i-1] if i > 0 else 0\n",
    "            else:\n",
    "                dp[i] = 1+i-dp[i-1]\n",
    "        return (sum(dp))%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        prefix = deque(accumulate(arr))\n",
    "        odd,even = 0,0\n",
    "        m = 1000000007\n",
    "        for i in prefix:\n",
    "            if i&1: odd  += 1\n",
    "            else:   even += 1\n",
    "        res = odd\n",
    "        for p in arr:\n",
    "            if p & 1:\n",
    "                odd -= 1\n",
    "                odd,even = even,odd\n",
    "            else:\n",
    "                even -= 1\n",
    "            res += odd\n",
    "        return res%m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(arr)\n",
    "        odd = [0] * (n + 1) \n",
    "        even = [0] * (n + 1)\n",
    "        for i in range(1,n+1):\n",
    "            if arr[i-1] % 2 == 0:\n",
    "                odd[i] = max(odd[i-1], odd[i])\n",
    "                even[i] = max(even[i-1] + 1, even[i])\n",
    "            else:\n",
    "                odd[i] = max(even[i-1] + 1, odd[i])\n",
    "                even[i] = max(odd[i-1], even[i])\n",
    "        #print(odd,even)\n",
    "        return sum(odd) % mod \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        n = len(arr) \n",
    "        odd=[0]*n  \n",
    "        even=[0]*n \n",
    "        if arr[0]&1==1 : \n",
    "            odd[0]=1\n",
    "            even[0]=0 \n",
    "        else:\n",
    "            odd[0]=0\n",
    "            even[0]=1 \n",
    "        for i in range(1,n): \n",
    "            if arr[i]&1==1: \n",
    "                odd[i]= 1+even[i-1] \n",
    "                even[i]=odd[i-1]\n",
    "            else:\n",
    "                odd[i]=odd[i-1]\n",
    "                even[i]=1+even[i-1] \n",
    "        return sum(odd)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        odd = [0] * 100001\n",
    "        even = [0] * 100001\n",
    "        p = 1000000007\n",
    "        for i in range(len(arr)):\n",
    "            if(arr[i] & 1):\n",
    "                 odd[i] = (even[i - 1] + 1) % p\n",
    "                 even[i] = odd[i - 1]\n",
    "            else:\n",
    "                even[i] = (even[i - 1] + 1) % p\n",
    "                odd[i] = odd[i - 1]\n",
    "        return sum(odd) % p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        limit = 1000000000+7\n",
    "        from itertools import accumulate\n",
    "        arr1 = list(accumulate(arr))\n",
    "        arr1.insert(0,0)\n",
    "\n",
    "        odd, even = 0, 0\n",
    "        count = 0\n",
    "        for i in arr1:\n",
    "            if i%2:\n",
    "                odd += 1\n",
    "                count += even%limit\n",
    "            else:\n",
    "                even += 1\n",
    "                count += odd%limit\n",
    "        return count%limit\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        sums = [0]\n",
    "        odd = 0\n",
    "        even = 0\n",
    "        for i in range(len(arr)):\n",
    "            sums.append(sums[-1] + arr[i])\n",
    "            if sums[-1] % 2 == 0:\n",
    "                even += 1\n",
    "            else:\n",
    "                odd += 1\n",
    "        return int((odd + odd*even) % (1e9+7))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        sums = [0]\n",
    "        odd = 0\n",
    "        even = 0\n",
    "        for i in range(len(arr)):\n",
    "            sums.append(sums[-1] + arr[i])\n",
    "            if sums[-1] % 2 == 0:\n",
    "                even += 1\n",
    "            else:\n",
    "                odd += 1\n",
    "        return int((odd + odd*even) % (1e9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        a = [0]*len(arr)\n",
    "        if arr[0]%2==1:\n",
    "            a[0] = 1\n",
    "        n = 2\n",
    "        for i in range(1,len(arr)):\n",
    "            if arr[i]%2==1:\n",
    "                a[i] = (n-a[i-1])%(1000000007)\n",
    "            else:\n",
    "                a[i] = (a[i-1])%(1000000007)\n",
    "            n+=1\n",
    "        return sum(a)%(1000000007)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        odd = []\n",
    "        even = []\n",
    "        if arr[0] % 2:\n",
    "            odd.append(1)\n",
    "            even.append(0)\n",
    "        else:\n",
    "            odd.append(0)\n",
    "            even.append(1)\n",
    "        for num in arr[1:]:\n",
    "            if num % 2:\n",
    "                odd.append(even[-1]+1)\n",
    "                even.append(odd[-2])\n",
    "            else:\n",
    "                odd.append(odd[-1])\n",
    "                even.append(even[-1]+1)\n",
    "        return sum(odd) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        sums = [0]\n",
    "        odd = 0\n",
    "        even = 0\n",
    "        for i in range(len(arr)):\n",
    "            sums.append(sums[-1] + arr[i])\n",
    "            if sums[-1] % 2 == 0:\n",
    "                even += 1\n",
    "            else:\n",
    "                odd += 1\n",
    "        return int((odd + odd*even) % (1e9+7))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        arrl = len(arr)\n",
    "        ans = [0 for i in range(0, arrl+1)]\n",
    "        odd = 0\n",
    "        even = 1\n",
    "        res = 0\n",
    "        MOD = 10**9 + 7\n",
    "        for i in range(1, arrl+1):\n",
    "            ans[i] = ans[i-1] + arr[i-1]\n",
    "            res = (res + (even if ans[i]%2 == 1 else odd))%MOD\n",
    "            if ans[i] % 2 == 1:\n",
    "                odd = odd + 1\n",
    "            else:\n",
    "                even = even + 1\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        sums = [0]\n",
    "        odd = 0\n",
    "        even = 0\n",
    "        for i in range(len(arr)):\n",
    "            sums.append(sums[-1] + arr[i])\n",
    "            if sums[-1] % 2 == 0:\n",
    "                even += 1\n",
    "            else:\n",
    "                odd += 1\n",
    "        return int((odd + odd*even) % (1e9+7))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        sums = [0]\n",
    "        odd = 0\n",
    "        even = 0\n",
    "        for i in range(len(arr)):\n",
    "            sums.append(sums[-1] + arr[i])\n",
    "            if sums[-1] % 2 == 0:\n",
    "                even += 1\n",
    "            else:\n",
    "                odd += 1\n",
    "        return int((odd + odd*even) % (1e9+7))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        sums = [0] * len(arr)\n",
    "        sums[0] = arr[0]\n",
    "        odd = 0  # 前缀和数组中奇数元素的数量\n",
    "        even = 0  # 前缀和数组中偶数元素的数量\n",
    "        if sums[0] % 2 == 1:\n",
    "            odd += 1\n",
    "        else:\n",
    "            even += 1\n",
    "        MOD = 1e9 + 7\n",
    "        for i in range(1, len(arr)):\n",
    "            sums[i] = sums[i - 1] + arr[i]  # 计算前缀和\n",
    "            if sums[i] % 2 == 1:  # 当前元素为奇数\n",
    "                odd += 1\n",
    "            else:  # 偶数\n",
    "                even += 1\n",
    "        return int((odd + odd*even) % MOD)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        ans = 0\n",
    "        pre = [0] + list(accumulate(arr))\n",
    "        cnt = [0] * 2\n",
    "        cnt[0] = 1\n",
    "        for i in range(len(arr)):\n",
    "            cur = pre[i + 1] & 1\n",
    "            ans = (cnt[cur ^ 1] + ans) % (10**9 + 7)\n",
    "            cnt[cur] += 1\n",
    "        return ans\n",
    "            \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        dp_odd = [0] * len(arr)\n",
    "        dp_even = [0] * len(arr)\n",
    "        if arr[0] % 2 == 0:\n",
    "            dp_even[0] = 1\n",
    "        else:\n",
    "            dp_odd[0] = 1\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i] % 2 == 0:\n",
    "                dp_odd[i] = dp_odd[i-1]\n",
    "                dp_even[i] = dp_even[i-1] + 1\n",
    "            else:\n",
    "                dp_odd[i] = dp_even[i-1] + 1\n",
    "                dp_even[i] = dp_odd[i-1]\n",
    "        return sum(dp_odd) % (10**9 + 7)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr):\n",
    "        changdu=len(arr)\n",
    "        heweijishudegeshu=[0]*changdu\n",
    "        heweioushudegeshu=[0]*changdu\n",
    "        if arr[0]%2==1:\n",
    "            heweijishudegeshu[0]=1\n",
    "        else:\n",
    "            heweioushudegeshu[0]=1\n",
    "        for i in range(1,changdu):\n",
    "            shangyige_hewei_jishu_de_geshu = heweijishudegeshu[i-1]\n",
    "            shangyige_hewei_oushu_de_geshu = heweioushudegeshu[i-1]\n",
    "            if arr[i]%2==1:\n",
    "                heweijishudegeshu[i] = 1+ shangyige_hewei_oushu_de_geshu\n",
    "                heweioushudegeshu[i]=shangyige_hewei_jishu_de_geshu\n",
    "            else:\n",
    "                heweijishudegeshu[i] = shangyige_hewei_jishu_de_geshu\n",
    "                heweioushudegeshu[i] = 1+shangyige_hewei_oushu_de_geshu\n",
    "        \n",
    "        res=0\n",
    "        for i in heweijishudegeshu:\n",
    "            res+=i\n",
    "            res%=1000000007\n",
    "        print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        #DP思路\n",
    "        #奇+偶==奇\n",
    "        #偶+奇==奇\n",
    "        #dp[i]表示以arr[i]结尾的子数组且和为奇数的个数\n",
    "        dp=[0]*n\n",
    "        #dp[i]表示以arr[i]结尾的子数组且和为偶数的个数\n",
    "        op=[0]*n\n",
    "        #判断奇偶(位运算版)\n",
    "        if arr[0]&1:\n",
    "            dp[0]=1\n",
    "        else:\n",
    "            op[0]=1\n",
    "        ans=dp[0]\n",
    "        for i in range(1,n):\n",
    "            if arr[i]&1:\n",
    "                op[i]=dp[i-1]\n",
    "                dp[i]=op[i-1]+1\n",
    "            else:\n",
    "                dp[i]=dp[i-1]\n",
    "                op[i]=op[i-1]+1\n",
    "            ans+=dp[i]\n",
    "        return ans%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        #明天想前缀和计数思路\n",
    "        n=len(arr)\n",
    "        #DP思路,状态转移搞清楚\n",
    "        #奇+偶==奇\n",
    "        #偶+奇==奇\n",
    "        #dp[i]表示以arr[i]结尾的子数组且和为奇数的个数\n",
    "        dp=[0]*n\n",
    "        #dp[i]表示以arr[i]结尾的子数组且和为偶数的个数\n",
    "        op=[0]*n\n",
    "        #判断奇偶(位运算版)\n",
    "        if arr[0]&1:\n",
    "            dp[0]=1\n",
    "        else:\n",
    "            op[0]=1\n",
    "        ans=dp[0]\n",
    "        for i in range(1,n):\n",
    "            if arr[i]&1:\n",
    "                op[i]=dp[i-1]\n",
    "                dp[i]=op[i-1]+1\n",
    "            else:\n",
    "                dp[i]=dp[i-1]\n",
    "                op[i]=op[i-1]+1\n",
    "            ans+=dp[i]\n",
    "        return ans%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        odd[i]以arr[i]结尾的和为偶数的子数组数目\n",
    "        even[i]以arr[i]结尾的和为奇数的子数组数目\n",
    "        \"\"\"\n",
    "        even = [0]*len(arr)\n",
    "        odd = [0]*len(arr)\n",
    "        if arr[0]%2 ==0:\n",
    "            odd[0] = 1\n",
    "        else:\n",
    "            even[0] = 1\n",
    "        for i in range(1,len(arr)):\n",
    "            if arr[i] %2 == 0:\n",
    "                even[i] += even[i-1]\n",
    "                odd[i]+=odd[i-1]+1\n",
    "            else:# arr[i] %2 == 1:\n",
    "                odd[i] +=  even[i-1]\n",
    "                even[i]+=odd[i-1]+1\n",
    "        return sum(even)%(1000000007)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        #DP思路\n",
    "        #奇+偶==奇\n",
    "        #偶+奇==奇\n",
    "        #dp[i]表示以arr[i]结尾的子数组且和为奇数的个数\n",
    "        dp=[0]*n\n",
    "        #dp[i]表示以arr[i]结尾的子数组且和为偶数的个数\n",
    "        op=[0]*n\n",
    "        #判断奇偶(位运算版)\n",
    "        if arr[0]&1:\n",
    "            dp[0]=1\n",
    "        else:\n",
    "            op[0]=1\n",
    "        ans=dp[0]\n",
    "        for i in range(1,n):\n",
    "            if arr[i]&1:\n",
    "                op[i]=dp[i-1]\n",
    "                dp[i]=op[i-1]+1\n",
    "            else:\n",
    "                dp[i]=dp[i-1]\n",
    "                op[i]=op[i-1]+1\n",
    "            ans+=dp[i]\n",
    "        return ans%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "\n",
    "        n = len(arr)\n",
    "        pre = [0]\n",
    "        for i in range(n):\n",
    "            pre.append(pre[-1] + arr[i])\n",
    "        \n",
    "        hashmap = collections.defaultdict(list)\n",
    "        for i in range(n + 1):\n",
    "            hashmap[pre[i] % 2].append(i)\n",
    "        if 1 not in hashmap: return 0\n",
    "        res = 0\n",
    "        m, n = len(hashmap[0]), len(hashmap[1])\n",
    "        \n",
    "        return (m * n) % int(1e9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        j = [0]* len(arr)\n",
    "        o = [0]* len(arr)\n",
    "        if arr[0] %2 != 0:\n",
    "            j[0] = 1\n",
    "        else:\n",
    "            o[0] = 1\n",
    "        for i in range(1,len(arr)):\n",
    "            if arr[i]%2 == 1:\n",
    "                j[i] += o[i-1]+1\n",
    "                o[i] += j[i-1]\n",
    "            else:\n",
    "                o[i] += o[i-1]+1\n",
    "                j[i] += j[i-1]\n",
    "        return sum(j)%(1000000007)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        ans = [[0],[0]]\n",
    "        length = len(arr)\n",
    "        for i in range(length):\n",
    "            if arr[i]%2:\n",
    "                ans[0].append(ans[1][i]+1)\n",
    "                ans[1].append(ans[0][i])\n",
    "            else:\n",
    "                ans[0].append(ans[0][i])\n",
    "                ans[1].append(ans[1][i]+1)\n",
    "        return sum(ans[0])%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        ans = [[0],[0]]\n",
    "        length = len(arr)\n",
    "        for i in range(length):\n",
    "            if arr[i]%2:\n",
    "                ans[0].append(ans[1][i]+1)\n",
    "                ans[1].append(ans[0][i])\n",
    "            else:\n",
    "                ans[0].append(ans[0][i])\n",
    "                ans[1].append(ans[1][i]+1)\n",
    "        return sum(ans[0])%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        ans = [[0],[0]]\n",
    "        length = len(arr)\n",
    "        for i in range(length):\n",
    "            if arr[i]%2:\n",
    "                ans[0].append(ans[1][i]+1)\n",
    "                ans[1].append(ans[0][i])\n",
    "            else:\n",
    "                ans[0].append(ans[0][i])\n",
    "                ans[1].append(ans[1][i]+1)\n",
    "        return sum(ans[0])%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        ans = 0\n",
    "        sum_arr = [0]\n",
    "        for i in arr:\n",
    "            sum_arr.append(sum_arr[-1]+i)\n",
    "        # print(sum_arr)\n",
    "        odd_counts = [0]\n",
    "        even_counts = [0]\n",
    "        for i in sum_arr[1:]:\n",
    "            if i%2==0:\n",
    "                odd_counts.append(odd_counts[-1])\n",
    "                even_counts.append(even_counts[-1]+1)\n",
    "            else:\n",
    "                odd_counts.append(odd_counts[-1]+1)\n",
    "                even_counts.append(even_counts[-1])\n",
    "        # print(odd_counts)\n",
    "        # print(even_counts)\n",
    "        for i in range(len(arr)):\n",
    "            if sum_arr[i] % 2==0: # 如果是当前和是偶数\n",
    "                ans += (odd_counts[-1] - odd_counts[i])\n",
    "            else:\n",
    "                ans += (even_counts[-1] - even_counts[i])\n",
    "        # print(ans)\n",
    "        return ans % (1000000000 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        ji, ou = [0] * (len(arr)+1), [0] * (len(arr)+1)\n",
    "        if arr[0] % 2 == 0:\n",
    "            ou[0] = 1\n",
    "            flag = False\n",
    "        else:\n",
    "            ji[0] = 1\n",
    "            flag = True\n",
    "        \n",
    "        for i,n in enumerate(arr):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            if flag:\n",
    "                if n%2 == 0:\n",
    "                    ji[i] = 1\n",
    "                    \n",
    "                else:\n",
    "                    ou[i] = 1\n",
    "                    flag = False\n",
    "            else:\n",
    "                if n%2 != 0:\n",
    "                    ji[i] = 1\n",
    "                    flag = True\n",
    "                else:\n",
    "                    ou[i] = 1\n",
    "            ji[i] += ji[i-1]\n",
    "            ou[i] += ou[i-1]\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(len(arr)):\n",
    "            if ji[i] - ji[i-1] == 1:\n",
    "                res += ou[i] + 1\n",
    "            else:\n",
    "                res += ji[i]\n",
    "            res %= 1000000007\n",
    "        # print(ji)\n",
    "        # print(ou)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "预处理每个数字左边前缀和有几个奇数结果，几个偶数结果\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        presum = list(accumulate(arr,initial=0))\n",
    "        presum.pop(0)\n",
    "        cnt_odd = [0] * n #统计num左边有几个奇数前缀和\n",
    "        for i in range(1,n):\n",
    "            if presum[i-1] % 2 != 0:\n",
    "                cnt_odd[i] = cnt_odd[i-1] + 1\n",
    "            else:\n",
    "                cnt_odd[i] = cnt_odd[i-1]\n",
    "        s,res = 0,0\n",
    "        for i,num in enumerate(arr):\n",
    "            s += num\n",
    "            if s % 2 == 0:\n",
    "                res += cnt_odd[i]\n",
    "            else:\n",
    "                res += i-cnt_odd[i] + 1\n",
    "\n",
    "        return res%(10**9+7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        dp = [(0,0)]\n",
    "        res = 0\n",
    "        for num in arr:\n",
    "            #print(dp)\n",
    "            odd,even = dp[-1]\n",
    "            if num%2:\n",
    "                even,odd = odd,even+1\n",
    "            else:\n",
    "                even,odd = even+1,odd\n",
    "            res += odd\n",
    "            dp.append((odd,even))\n",
    "        return res%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        pre_arr=[0 for _ in range(n+1)]\n",
    "        summ=0\n",
    "        odds=set()\n",
    "        evens=set()\n",
    "        for i in range(n):\n",
    "            summ+=arr[i]\n",
    "            pre_arr[i+1]=summ%2\n",
    "            if pre_arr[i+1]==1:\n",
    "                odds.add(i)\n",
    "            else:\n",
    "                evens.add(i)\n",
    "\n",
    "        ret=0\n",
    "        '''\n",
    "        for i in range(n):\n",
    "            if i in odds:\n",
    "                ret+=1\n",
    "                for j in range(i):\n",
    "                    if j in evens:\n",
    "                        ret+=1\n",
    "            else:\n",
    "                for j in range(i):\n",
    "                    if j in odds:\n",
    "                        ret+=1\n",
    "        '''\n",
    "        n=len(odds)\n",
    "        m=len(evens)\n",
    "        ret=n+n*m\n",
    "        return ret%(10**9+7)\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        res = 0\n",
    "        odd, even = [0], [0]\n",
    "        n = len(arr)\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            count += arr[i]\n",
    "            if count % 2 == 0:\n",
    "                odd.append(odd[i])\n",
    "                even.append(even[i] + 1)\n",
    "            else:\n",
    "                odd.append(odd[i] + 1)\n",
    "                even.append(even[i])\n",
    "            arr[i] = count\n",
    "        for i in range(n):\n",
    "            if arr[i] % 2 == 0:\n",
    "                res += odd[i+1]\n",
    "            else:\n",
    "                res += even[i+1] + 1\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, a: List[int]) -> int:\n",
    "        if not a or len(a) == 0:\n",
    "            return 0\n",
    "        n = len(a)\n",
    "        mod = 7 + 10**9\n",
    "        j, o = [0] * (n + 1), [0] * (n + 1)\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            lj, lo = j[i - 1], o[i - 1]\n",
    "            if a[i - 1] % 2 == 0:\n",
    "                j[i] += lj\n",
    "                o[i] += 1 + lo\n",
    "            elif a[i - 1] % 2 == 1:\n",
    "                j[i] += 1 + lo\n",
    "                o[i] += lj\n",
    "            j[i] = j[i] % mod\n",
    "            o[i] = o[i] % mod\n",
    "        return sum(j) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(arr)\n",
    "        odd = [0] * (n + 1)\n",
    "        even = [0] * (n + 1)\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            if arr[i-1] % 2 == 0:\n",
    "                odd[i] = odd[i-1]\n",
    "                even[i] = 1 + even[i-1]          \n",
    "            elif arr[i-1] % 2 == 1:\n",
    "                odd[i] = 1 + even[i-1]\n",
    "                even[i] = odd[i-1]\n",
    "\n",
    "            odd[i] = odd[i] % mod\n",
    "            even[i] = even[i] % mod\n",
    "\n",
    "        return sum(odd) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        length=len(arr)\n",
    "        for i in range(length):\n",
    "            arr[i]=arr[i]%2\n",
    "        pre_num=[]#前缀和\n",
    "        ji_pre_num=[]#奇数前缀和个数\n",
    "        ans=0\n",
    "        pre_num.append(arr[0])\n",
    "        ji_pre_num.append(arr[0])\n",
    "        for i in range(1,length):\n",
    "            pre_num.append(pre_num[i-1]+arr[i])\n",
    "            ji_pre_num.append(ji_pre_num[i-1]+pre_num[i]%2)\n",
    "        # print(pre_num)\n",
    "        # print(ji_pre_num)\n",
    "        ans=0\n",
    "        for i in range(length):\n",
    "            if pre_num[i]%2==0:\n",
    "                ans+=ji_pre_num[i]\n",
    "            else:\n",
    "                ans+=(i+1-ji_pre_num[i])\n",
    "            ans+=pre_num[i]%2\n",
    "            # print(i,ans)\n",
    "        return ans%(10**9+7)\n",
    "            # ans+=ji_num[i]%2\n",
    "        # for i in range(length):\n",
    "        #     for t in range(i+1,length):\n",
    "        #         ans+= (ji_num[t]-ji_num[i])%2\n",
    "        # return ans%(10**9+7)\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(arr)\n",
    "\n",
    "        even = [0] * n\n",
    "        odd = [0] * n\n",
    "\n",
    "        if arr[0] % 2 == 0:\n",
    "            even[0] = 1\n",
    "        else:\n",
    "            odd[0] = 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if arr[i] % 2 == 0:\n",
    "                odd[i] = odd[i - 1]\n",
    "                even[i] = even[i - 1] + 1\n",
    "            else:\n",
    "                odd[i] = even[i - 1] + 1\n",
    "                even[i] = odd[i - 1]\n",
    "            odd[i] %= mod\n",
    "            even[i] %= mod\n",
    "        \n",
    "        return sum(odd) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        dp=[[0,0] for _ in range(n+1)]\n",
    "        for i in range(1,n+1):\n",
    "            num=arr[i-1]\n",
    "            if num%2==1:\n",
    "                dp[i][0]=dp[i-1][1]\n",
    "                dp[i][1]=dp[i-1][0]+1\n",
    "            else:\n",
    "                dp[i][0]=dp[i-1][0]+1\n",
    "                dp[i][1]=dp[i-1][1]\n",
    "        ans=0\n",
    "        for i in range(n+1):\n",
    "            ans+=dp[i][1]\n",
    "        return ans%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        su,cnt =0,0\n",
    "        #基数 奇数-偶数 偶数-奇数\n",
    "        odd_set =set()\n",
    "        even_set =set()\n",
    "        for i in range(len(arr)):\n",
    "            su += arr[i]\n",
    "            if su % 2 ==1:\n",
    "                cnt +=1\n",
    "                cnt += len(even_set)\n",
    "                odd_set.add(su)\n",
    "            else:\n",
    "                cnt += len(odd_set)\n",
    "                even_set.add(su)\n",
    "        return cnt%(int(1e9+7))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        # dp[i][0] 和 dp[i][1]分别记录以arr[i]结尾的\"偶数、奇数和\"子数组数量\n",
    "        dp = [[0, 0] for _ in range(len(arr))]\n",
    "        dp[0] = [int(not arr[0] & 1), int(arr[0] & 1)]  # base-case\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i] & 1:\n",
    "                # 奇数加奇数变偶数，否则变奇数(加一)\n",
    "                dp[i] = [dp[i - 1][1], dp[i - 1][0] + 1]\n",
    "            else:\n",
    "                dp[i] = [dp[i - 1][0] + 1, dp[i - 1][1]]\n",
    "        return sum([dp[i][1] for i in range(len(arr))]) % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        qzh = [0]\n",
    "        d = dict()\n",
    "        d[0] = []\n",
    "        d[1] = []\n",
    "        ans = 0\n",
    "        for i in range(len(arr)):\n",
    "            qzh.append(qzh[-1] + arr[i])\n",
    "        for i in range(len(arr) + 1):\n",
    "            d[qzh[i] % 2].append(i)\n",
    "            ans += len(d[1 - (qzh[i] % 2)])\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "\n",
    "        array_length = len(arr) + 1\n",
    "\n",
    "        pre_sum = [0] * array_length\n",
    "        pre_even_num_sum = [0] * array_length\n",
    "        pre_odd_num_sum = [0] * array_length\n",
    "\n",
    "        even_sum = 0\n",
    "\n",
    "        for index, value in enumerate(arr):\n",
    "            pre_sum[index + 1] = pre_sum[index] + value\n",
    "            if pre_sum[index + 1] % 2 == 1:\n",
    "                pre_even_num_sum[index + 1] = pre_even_num_sum[index] + 1\n",
    "                pre_odd_num_sum[index + 1] = pre_odd_num_sum[index]\n",
    "                even_sum += 1\n",
    "                even_sum += pre_odd_num_sum[index + 1]\n",
    "            else:\n",
    "                pre_even_num_sum[index + 1] = pre_even_num_sum[index]\n",
    "                pre_odd_num_sum[index + 1] = pre_odd_num_sum[index] + 1\n",
    "                even_sum += pre_even_num_sum[index + 1]\n",
    "\n",
    "\n",
    "        return int(even_sum %(1e9 +7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        arr = [x%2 for x in arr]\n",
    "        \n",
    "        dp = [[0,0] for _ in range(len(arr))]\n",
    "        if arr[0]:\n",
    "            dp[0] = [1,0]\n",
    "        else:\n",
    "            dp[0] = [0,1]\n",
    "        \n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i]:\n",
    "                dp[i][0] = dp[i-1][1]+1\n",
    "                dp[i][1] = dp[i-1][0]\n",
    "            else:\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][1] = dp[i-1][1]+1\n",
    "        return sum([x[0] for x in dp])%mod\n",
    "            \n",
    "            \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        if not arr:\n",
    "            return 0\n",
    "\n",
    "        # dp[i][0]: 第i个数加入能形成多少个偶数子数组\n",
    "        # dp[i][1]: 第i个数加入能形成多少个奇数子数组\n",
    "        dp = [[0, 0] for _ in range(len(arr))]\n",
    "        if arr[0] % 2 == 0:\n",
    "            dp[0][0] = 1\n",
    "        else:\n",
    "            dp[0][1] = 1\n",
    "\n",
    "        odd_cnt = dp[0][1]\n",
    "\n",
    "        for i in range(1, len(arr)):\n",
    "            if 1 == arr[i] % 2:\n",
    "                dp[i][0] = dp[i - 1][1]\n",
    "                dp[i][1] = dp[i - 1][0] + 1\n",
    "            else:\n",
    "                dp[i][0] = dp[i - 1][0] + 1\n",
    "                dp[i][1] = dp[i - 1][1]\n",
    "\n",
    "            odd_cnt += dp[i][1]\n",
    "\n",
    "        print(\"Odd sub arr num \", odd_cnt)\n",
    "        return odd_cnt % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numOfSubarrays(self, arr):\n",
    "        dp = [[0,0] for _ in range(len(arr))]\n",
    "        if arr[0]%2 == 1:\n",
    "            dp[0] = [0,1]\n",
    "        else:\n",
    "            dp[0] = [1,0]\n",
    "            \n",
    "        res = dp[0][1]  \n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i]%2 == 1:\n",
    "                dp[i][0] = dp[i-1][1]\n",
    "                dp[i][1] = dp[i-1][0] + 1\n",
    "            else:\n",
    "                dp[i][0] = dp[i-1][0] + 1\n",
    "                dp[i][1] = dp[i-1][1]\n",
    "            res += dp[i][1]\n",
    "            \n",
    "        return res%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        if arr[0] %2 == 0:\n",
    "            ans = [[0,1]]\n",
    "        else:\n",
    "            ans = [[1,0]]\n",
    "        if n == 1:return ans[0][0]\n",
    "        for i in range(1,n):\n",
    "            x,y = ans[-1]\n",
    "            if arr[i]%2 == 1:\n",
    "                ans.append([y+1,x])\n",
    "            else:\n",
    "                ans.append([x,y+1])\n",
    "        res = 0\n",
    "        for x in ans:\n",
    "            res += x[0]\n",
    "        return res %(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        f = [[0] * 2 for i in range(n + 1)]\n",
    "        mod = 10 ** 9 + 7\n",
    "        res = 0\n",
    "        for i in range(1, n + 1):\n",
    "            x = arr[i - 1]\n",
    "            if x % 2:\n",
    "                f[i][1] = (f[i - 1][0] + 1) % mod\n",
    "                f[i][0] = f[i - 1][1]\n",
    "            else:\n",
    "                f[i][0] = (f[i - 1][0] + 1) % mod\n",
    "                f[i][1] = f[i - 1][1]\n",
    "            res = (res + f[i][1]) % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        length = len(arr)\n",
    "        li = [[0,0] for i in range(length)]\n",
    "        if arr[0]%2==0:\n",
    "            li[0] = [0,1]\n",
    "        else:\n",
    "            li[0] = [1,0]\n",
    "        count = 0\n",
    "        count += li[0][0]\n",
    "        for i in range(1,length):\n",
    "            if arr[i]%2==0:\n",
    "                li[i][0] = li[i-1][0]\n",
    "                li[i][1] = li[i-1][1] + 1\n",
    "                count += li[i][0]\n",
    "            else:\n",
    "                li[i][0] = li[i-1][1] + 1\n",
    "                li[i][1] = li[i-1][0]\n",
    "                count += li[i][0]\n",
    "        return count%(10**9+7)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[0] * 2 for _ in range(n)]\n",
    "        if arr[0] % 2 == 0:\n",
    "            dp[0][0] = 1\n",
    "        else: dp[0][1] = 1\n",
    "        res = dp[0][1]\n",
    "        for i in range(1, n):\n",
    "            if arr[i] % 2 != 0:\n",
    "                dp[i][0] = dp[i - 1][1]\n",
    "                dp[i][1] = dp[i - 1][0] + 1\n",
    "            else:\n",
    "                dp[i][0] = dp[i - 1][0] + 1\n",
    "                dp[i][1] = dp[i - 1][1]\n",
    "            res += dp[i][1]\n",
    "        return res % (10**9 + 7)\n",
    "\n",
    "\n",
    "\n",
    "# class Solution(object):\n",
    "#     def numOfSubarrays(self, arr):\n",
    "#         dp = [[0,0] for _ in range(len(arr))]\n",
    "#         if arr[0]%2 == 1:\n",
    "#             dp[0] = [0,1]\n",
    "#         else:\n",
    "#             dp[0] = [1,0]\n",
    "            \n",
    "#         res = dp[0][1]  \n",
    "#         for i in range(1, len(arr)):\n",
    "#             if arr[i]%2 == 1:\n",
    "#                 dp[i][0] = dp[i-1][1]\n",
    "#                 dp[i][1] = dp[i-1][0] + 1\n",
    "#             else:\n",
    "#                 dp[i][0] = dp[i-1][0] + 1\n",
    "#                 dp[i][1] = dp[i-1][1]\n",
    "#             res += dp[i][1]\n",
    "            \n",
    "#         return res%(10**9+7)\n",
    "\n",
    "# 作者：YZBoostForest\n",
    "# 链接：https://leetcode-cn.com/problems/number-of-sub-arrays-with-odd-sum/solution/dong-tai-gui-hua-on-python-by-yzboostfor-7hmt/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        nums = [0]\n",
    "        v = 0\n",
    "        for x in arr:\n",
    "            v += x\n",
    "            nums.append(v)\n",
    "        res = 0\n",
    "        modd = int(1e9) + 7\n",
    "        dp = [(0, 0)] * (n + 1)\n",
    "        # 初始化\n",
    "        for i in range(1, len(dp)):\n",
    "            v = arr[i - 1]\n",
    "            if v % 2 == 0:\n",
    "                # \n",
    "                a,b = dp[i-1]\n",
    "                dp[i] = (a,b+1)\n",
    "            else:\n",
    "                a, b = dp[i - 1]\n",
    "                dp[i] = (b+1, a)\n",
    "            res += dp[i][0]\n",
    "            res = res % modd\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        # 子数组 奇数个奇数 k个偶数\n",
    "        n = len(arr)\n",
    "        # 如果当前值为奇数，那么以此奇数为结尾的子数组个数为\n",
    "        # 上一个数字的子数组个数\n",
    "        dp = [[0] * 2 for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            if i == 0:\n",
    "                if x % 2: dp[i][0] = 1\n",
    "                else: dp[i][1] = 1\n",
    "            else:\n",
    "                if x % 2:\n",
    "                    dp[i][0] = dp[i - 1][1] + 1\n",
    "                    dp[i][1] = dp[i - 1][0]\n",
    "                else:\n",
    "                    dp[i][0] = dp[i - 1][0]\n",
    "                    dp[i][1] = dp[i - 1][1] + 1\n",
    "            ans += dp[i][0]\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        dp[i][0] / dp[i][1]: 以i元素结尾的 和为 偶数/奇数 的子数组的数量\n",
    "        i:[0, n-1], dp[0][0]=int(arr[0]%2==0); dp[0][1]=int(arr[0]%2!=0)\n",
    "        arr[i]为偶数 / arr[i]为奇数 分别讨论\n",
    "        \"\"\"\n",
    "        mod = 10**9 + 7\n",
    "        n = len(arr)\n",
    "        dp = [[0]*2 for _ in range(n)]\n",
    "        dp[0][0] = int(arr[0] % 2 == 0)\n",
    "        dp[0][1] = int(arr[0] % 2 != 0)\n",
    "\n",
    "        ans = int(dp[0][1]==1)\n",
    "        for i in range(1, n):\n",
    "            if arr[i] % 2 == 0:  # arr[i] 为偶数\n",
    "                # 偶+偶=偶, 偶+奇=奇\n",
    "                dp[i][0] = dp[i-1][0] + 1\n",
    "                dp[i][1] = dp[i-1][1]\n",
    "            else:\n",
    "                # arr[i] 为奇数\n",
    "                # 奇+奇=偶, 奇+偶=奇\n",
    "                dp[i][0] = dp[i-1][1]\n",
    "                dp[i][1] = dp[i-1][0] + 1\n",
    "            ans += dp[i][1]\n",
    "            ans %= mod\n",
    "\n",
    "        # print(dp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int]) -> int:\n",
    "        f=[[0,0] for i in range(len(arr)+1)]\n",
    "\n",
    "        cnt=0\n",
    "\n",
    "        ans=0\n",
    "        for i in range(0,len(arr)):\n",
    "            index=i+1\n",
    "            \n",
    "            if(arr[i]%2==0):#偶数\n",
    "               \n",
    "                f[index][1]=f[index-1][1]\n",
    "                f[index][0]=1+f[index-1][0]\n",
    "            else:#奇数\n",
    "              \n",
    "                f[index][1]=f[index-1][0]+1\n",
    "                f[index][0]=f[index-1][1]\n",
    "\n",
    "            #print(f)\n",
    "            cnt+=(f[index][1]%(1e9+7))\n",
    "            cnt%=(1e9+7)\n",
    "        \n",
    "        return int(cnt)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
